02/02/2021

Espaço de busca

  • Escala:
    • Continua:
      • Existem infinitas coordenadas de possíveis localizações para os Pa’s tornando o problema computacionalmente insolúvel.
    • Discreta:
      • Considerando a área de 800 x 800 metros discretizada em inteiros, existem 640.000 possíveis localizações para os Pa’s tornando o problema computacionalmente solúvel.

Desenho do Algoritmo

  • Testes dos Espaços:
    • Espaços discretos menores que 8 x 8 não apresentaram solução ótima.
    • Espaços maiores que 150 x 150 apresentaram convergência estável e aumento do custo computacional.
  • Implementação:
    • O algorítimo foi desenhado para escanear os espaços discretos de 8 x 8 até 150 x 150 na área de 800 x 800 com intervalos iguais entre os pontos.
    • Para ilustrar, foi considerado o espaço de 9 x 9, que representa 81 possíveis localizações para os Pa’s.

Interações do Algoritmo

  • Laço:
    • A cada iteração o algoritmo inspeciona cada coordenada do espaço discretizado de possíveis localizações dos Pa’s e determina o PA que cobre o maior número de Pd’s.
    • Se a condição de 150 Mbps não for violada, o índice do PA com maior cobertura de Pd’s é armazenado e esses Pd’s são removidos.
    • O algoritmo reinicia a busca do próximo PA que cobre mais Pd’s dentre os restantes.
  • Critério de Parada:
    • O algoritmo para quando cobre pelo menos 475 dos 500 Pd’s atendendo as restrições de consumo de banda e limite de Pa’s.

Primeira Iteração

  • O algoritmo conta o número de Pd’s cobertos por cada uma das 81 possíveis localizações para o 1º PA e soma os Mbps demandados.

  • O máximo de 202 Pd’s são cobertos pelo PA nas coordenadas (200, 200).

  • O total de 146 Mbps de demanda desses Pd’s não viola a condição de menor que 150 Mbps.

  • As coordenadas deste 1º PA são armazenadas.

  • Os 202 Pd’s cobertos por este PA são removidos por já estarem cobertos.

Segunda Iteração

  • O algoritmo realiza a mesma busca e contagem da primeira iteração, porém desconsiderando os Pd’s cobertos pelo 1º PA.

  • O máximo de 199 Pd’s são cobertos pelo PA nas coordenadas (600, 600).

  • O total de 141 Mbps de demanda destes Pd’s não viola a condição de menor que 150 Mbps.

  • Da mesma forma são armazenadas as coordenadas desse 2º PA.

  • Os 199 Pd’s cobertos por este PA também são removidos por já estarem cobertos.

Decima Sétima Iteração

  • O algoritmo para.

  • O resultado da busca retorna uma solução no mínimo local de 17 PA´s.

  • A condição de que 95% ou 475 do total de 500 pontos sejam cobertos é atendida.

  • A restrição de que a soma da demanda dos Pd’s cobertos por um Pa não exceda 150 Mbps é atendida.

  • As informações dos índices, número de Pd’s atendidos e total da demanda em Mbps de cada Pa podem ser recuperados.

Conclusões:

  • O algoritmo foi aplicado em todas as cobinações de espaços discretos entre 8 x 8 até 150 x 150.

  • O algoritmo encontra mínimos locais entre 20 e 13 Pa’s em espaços discretos com intervalo entre 8 x 8 até 54 x 54.

  • O algoritmo oscila entre 12 e 13 Pa’s em espaços discretos no intervalo entre 55 x 55 até 114 x 114.

  • O algoritmo converge para o mínimo global de 12 Pa’s em espaços mais granulares que 115 x 115.